//组合总数IV（medium): https://leetcode.cn/problems/combination-sum-iv/
class Solution
{
public:
	int combinationSum4(vector<int>& nums, int target)
	{
		vector<double> dp(target + 1);
		dp[0] = 1;
		for (int i = 1; i <= target; i++)
		{
			for (auto x : nums)
			{
				if (x <= i)
				{
					dp[i] += dp[i - x];
				}
			}
				
		}
			
		return dp[target];
	}
};

//不同的⼆叉搜索树（medium）: https://leetcode.cn/problems/unique-binary-search-trees/
class Solution
{
public:
	int numTrees(int n)
	{
		vector<int> dp(n + 1, 0); // dp[i] 表⽰：当结点的数量为 i 个的时候，⼀共有多少颗 BST
		dp[0] = 1; // 空树也是⼀颗⼆叉搜索树
		for (int i = 1; i <= n; i++) // 枚举结点的总数
		{
			for (int j = 1; j <= i; j++) // 选择每⼀个根节点
			{
				dp[i] += dp[j - 1] * dp[i - j]; // ⼆叉树总量累加在⼀起
			}
		}

		return dp[n];
	}
};